#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


bool isPalindrome(vector<int>& nums){
    int n = nums.size();
    int left;
    int right;
    if(n % 2){
        left = (n-1) / 2 - 1;
        right = (n-1) / 2 + 1;
        while(left >=0 && right <n){
            if(nums[left] != right) return 0;
            left--;
            right++;
        }
    }else{
        left = (n-1) / 2;
        right = left+1;
        while(left>=0 && right < n){
            if(nums[left] != nums[right]) return 0;
            --left;
            ++right;
        }
    }
    return 1;
}

bool isSymmetric(TreeNode* root) {
    if(root == nullptr) return 1;
    queue<TreeNode*> Q;
    Q.push(root);
    while(!Q.empty()){
        int size = Q.size();
        vector<int> nums;
        for(int i=0;i<size;i++){
            if(Q.front()->left == nullptr){
                nums.push_back(-0x3f3f3f3f);
            }else{
                Q.push(Q.front()->left);
                nums.push_back(Q.front()->left->val);
            }
            if(Q.front()->right == nullptr){
                nums.push_back(-0x3f3f3f3f);
            }else{
                Q.push(Q.front()->right);
                nums.push_back(Q.front()->right->val);
            }
            Q.pop();
        }
        if(!isPalindrome(nums)) return 0;
    }
    return 1;
}

int main(){
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(3);
    bool ans = isSymmetric(root);
    cout << ans << endl;
    return 0;
}